#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <list>

using namespace std;

class Solution {
    /*
private:
    unordered_set<int> visited;
    unordered_map<int, vector<int>> route_map;
    bool search(int pre) {
        if (visited.count(pre) != 0) {
            return false;
        }
        visited.insert(pre);
        if (route_map.count(pre) != 0) {
            for (int dist : route_map[pre]) {
                if (route_map.count(dist) != 0) {
                    if (!search(dist)) {
                        return false;
                    }
                }
            }
        }
        visited.erase(pre);
        return true;
    }
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        for (vector<int> prerequisite : prerequisites) {
            if (route_map.count(prerequisite[0]) == 0) {
                route_map[prerequisite[0]] = {prerequisite[1]};
            } else {
                route_map[prerequisite[0]].push_back(prerequisite[1]);
            }
        }
        for (pair<int, vector<int>> route : route_map) {
            if (!search(route.first)) {
                return false;
            }
        }
        return true;
    }*/

private:
    vector<uint8_t> visited;
    vector<vector<int>> route_map;
    bool search(int pre) {
        if (visited[pre] == 2) {
            return true;
        }
        if (visited[pre]) {
            return false;
        }
        visited[pre] = 1;
       for (int val : route_map[pre]) {
           if (!search(val)) {
               return false;
           }
       }
       visited[pre] = 2;
       return true;
    }
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        route_map.resize(numCourses);
        visited.assign(numCourses, false);
        for (vector<int> prerequisite : prerequisites) {
            route_map[prerequisite[0]].push_back(prerequisite[1]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (!search(i)) {
                return false;
            }
        }
        return true;
    }
};

int main() {
    vector<vector<int>> input = {{1, 0}, {2, 6}, {1, 7}, {6, 4}, {7, 0}, {0, 5}};
    Solution solution;
    int output = solution.canFinish(8, input);
    cout << output << endl;
    return 0;
}